<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    // function xier(arr) {
    //   var interval = parseInt(arr.length / 2); //分组间隔设置
    //   while (interval > 0) {
    //     console.log("interval:"+interval)
    //     for (var i = interval; i < arr.length; i++) {
    //       var n = i;
    //       console.log(n + ': ' + arr[n])
    //       console.log(n - interval +': ' +arr[n - interval])
    //       while (arr[n] < arr[n - interval] && n > 0) {
    //         var temp = arr[n];
    //         arr[n] = arr[n - interval];
    //         arr[n - interval] = temp;
    //         n = n - interval;  
    //         console.log('交换')         
    //         console.log(arr)

    //       }
    //     }
    //     console.log(arr)
    //     interval = parseInt(interval / 2);
    //   }
    //   return arr;
    // }
    const shellSort = arr => {
      let len = arr.length,
        temp,
        gap = 1;
      console.time('希尔排序耗时');
      while (gap < len / 3) {
        //动态定义间隔序列
        gap = gap * 3 + 1;
      }
      for (gap; gap > 0; gap = Math.floor(gap / 3)) {
        console.log(gap)
        for (let i = gap; i < len; i++) {
          temp = arr[i];
          let j = i - gap;
          for (; j >= 0 && arr[j] > temp; j -= gap) {
            arr[j + gap] = arr[j];
          }
          arr[j + gap] = temp;
          console.log('arr  :', arr);
        }
      }
      console.timeEnd('希尔排序耗时');
      return arr;
    };
    let arr = [12,10,9,7,5,3,2,1,0]
    console.log(arr)
    // console.log(xier(arr))
    console.log(shellSort(arr))
  </script>
</body>

</html>